package source;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SlideWindow {
    /**
     * 长度最小的子数组
     * <p>
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * <p>
     * 找出该数组中满足其总和大于等于 target 的长度最小的 子数组
     * [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。
     *
     * @param target 正整数
     * @param nums   含有 n 个正整数的数组
     * @return 长度最小的子数组长度，如果不存在符合条件的子数组，返回 0 。
     */
    public int minSubArrayLen(int target, int[] nums) {
        int minLen = nums.length;
        int sum = 0;
        int i = 0, j = 0;
        boolean have = false;
        while (j < nums.length) {
            sum += nums[j];
            j++;
            while (i < j && sum >= target) {
                have = true;
                minLen = Math.min(j - i, minLen);
                sum -= nums[i];
                i++;
            }
        }
        if (have) {
            return minLen;
        } else
            return 0;
    }

    /**
     * 无重复字符的最长字串
     * <p>
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
     *
     * @param s 主串
     * @return 最长子串长度
     */
    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0;
        int len = s.length();
        int ans = 0;
        int tmp;
        boolean flag = false;
        while (j < len) {
            tmp = i;
            flag = true;
            while (tmp < j) {
                if (s.charAt(j) == s.charAt(tmp)) {
                    tmp++;
                    flag = false;
                    break;
                }
                tmp++;
            }
            if (flag) {
                j++;
                ans = Math.max(ans, j - i);
            } else {
                i = tmp;
            }
        }

        return ans;
    }

    /**
     * 给定一个字符串 s 和一个字符串数组 words。
     * words 中所有字符串 长度相同。
     * s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
     * 例如，如果 words = ["ab","cd","ef"]，
     * 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
     * "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
     * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
     *
     * @param s     字符串
     * @param words 字符串数组
     * @return 返回所有串联子串在 s 中的开始索引。
     */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (words.length == 0) return result;

        final int wordLen = words[0].length();
        final int totalLen = words.length * wordLen;
        if (s.length() < totalLen) return result;

        // 统计单词频率
        Map<String, Integer> wordCounts = new HashMap<>();

        for (String word : words) {
            wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
        }

        // 优化遍历范围
        for (int i = 0; i <= s.length() - totalLen; i++) {
            Map<String, Integer> currentCounts = new HashMap<>(wordCounts);
            int matched = 0;

            // 检查当前窗口
            for (int j = i; j < i + totalLen; j += wordLen) {
                String segment = s.substring(j, j + wordLen);
                Integer count = currentCounts.get(segment);

                if (count == null) break; // 遇到无效单词
                if (count == 0) break;    // 单词超量

                currentCounts.put(segment, count - 1);
                if (count == 1) matched++; // 完全消耗该单词
            }

            if (matched == currentCounts.size())
                result.add(i);
        }
        return result;
    }


    @Test
    public void testSubString() {
        String s = "wordgoodgoodgoodbestword";
        String[] words = new String[]{"word", "good", "best", "word"};
        System.out.println(findSubstring(s, words));
    }

    /**
     * 最小覆盖子串
     * <p>
     * 给你一个字符串 s 、一个字符串 t 。
     * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     *
     * @param s 字符串
     * @param t 模式串
     * @return 返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     */
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int min, max;
        int tLen = t.length();
        int sLen = s.length();
        int len = 0;
        int ansi = 0, ansj = sLen - 1;
        for (int i = 0; i < tLen; i++) {
            hashMap.put(t.charAt(i), hashMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        boolean isEmpty = true;
        int i = 0, j = 0;
        while (j < sLen) { // 后指针
            Integer value = hashMap.get(s.charAt(j));
            if (value != null) {
                if (value > 0) {
                    len++;
                    hashMap.put(s.charAt(j), value - 1);
                    if (len >= tLen) {
                        max = j;
                        while (i <= sLen - tLen) {  // 前指针
                            value = hashMap.get(s.charAt(i));
                            if (value != null) {
                                if (value >= 0) {
                                    min = i;
                                    if (max - min <= ansj - ansi) {
                                        ansi = min;
                                        ansj = max;
                                        isEmpty = false;
                                    }
                                    len--;
                                    hashMap.put(s.charAt(i), value + 1);
                                    i++;
                                    break;
                                }
                                hashMap.put(s.charAt(i), value + 1);
                            }
                            i++;
                        }
                    }
                } else {
                    hashMap.put(s.charAt(j), value - 1);
                }
            }
            j++;
        }
        if (isEmpty) {
            return "";
        }
        return s.substring(ansi, ansj + 1);
    }

    @Test
    public void testMinWindow() {
        String s = "a";
        String subString = "a";
        System.out.println(minWindow(s, subString));
    }

}
